package cn.edu.besti.cs1623.cw2324;

import java.util.LinkedList;

/**
 * Created by 春旺 on 2017/9/18.
 */
//********************************************************************
// Searching.java Java Foundations
//
// Contains various search algorithms that operate on an array of
// Comparable objects.
//********************************************************************
public class Searching {
    //-----------------------------------------------------------------
// Searches the specified array of objects using a linear search
// algorithm. Returns null if the target is not found.
//-----------------------------------------------------------------
    public static Comparable linearSearch(Comparable [] data , Comparable target){
        Comparable result = null ;
        int index = 0;
        while (result == null && index < data.length){
           if ( data[index].compareTo(target) == 0)
               result = data[index];
           index++;
        }
        return result;
    }
    //-----------------------------------------------------------------
// Searches the specified array of objects using a binary search
// algorithm. Returns null if the target is not found.
//-----------------------------------------------------------------
    public static  Comparable  binarySearch(Comparable[] data , Comparable target){
        Comparable result = null;
        int first = 1,last = data.length - 1,mid;

        while (result == null && first <= last){
            mid = (first + last) / 2; // determine midpoint
            if (data[mid].compareTo(target) == 0) {
                result =  data[mid];
            }
            else
                if (data[mid].compareTo(target)  > 0)
                    last = mid - 1;
            else
                first = mid + 1;

            }
            return  result;
        }
        /*
        * 插值查找
        * */
        public static Comparable insertionSearch(int [] data , int target){
        Comparable result = null;
            int first = 0,last = data.length - 1,mid;
            while (result == null && first <= last){
                mid =first + (first -last) * (target - data[first]) / (data[first] - data[last]);
                if (data[mid]==target){
                    result =  data[mid];
                }
                else
                if (data[mid] > target)
                    last = mid - 1;
                else
                    first = mid + 1;
            }
        return result;
        }
/*
* 斐波那契查找
* */
    public static Comparable fibonacciSearch(int[] data, int target) {
        Comparable result = null;
        int first = 0;
        int last = data.length - 1;
        int mid = 0;
        int k = 0;// 斐波那契分割数值的下标
        int i = 0; // 数组的元素个数
        int[] f = fibonacci();// 构造斐波那契数列
        ///获取斐波那契分割数值下标
        while (data.length > f[k] - 1) {
            k++;
        }
        // 创建临时数组
        int[] temp = new int[f[k] - 1];
        //将所有的元素赋给临时数组
        for (int j = 0; j < data.length;j++){
            temp[j] = data[j];
    }
    // 因为在一个数组的元素的个数n = F[k]-1是才能用斐波那契查找所以要补全。
    // 临时数组补充至f[k]个元素补充的元素值为临时数组的最后一个元素的值。
        for (i = data.length; i < f[k] - 1; i++) {
        temp[i] = temp[last];
    }
        while (first <= last) {
        // 前半部分有f[k-1]个元素，由于下标从0开始
        mid = first + f[k - 1] - 1;
        if (temp[mid] > target) {
            // 目标元素比参考元素小，向左查找，last的值变小
            last = mid - 1;
            //根据斐波那契数列特性 f[k] = f[k-1] + f[k-2]
            // 因为右半部分排除所以就去掉了f[k - 2]，所以 k = k-1
            k = k - 1;
        } else if (temp[mid] < target) {
            // 目标元素比参考元素大，向右查找，first的值变大
            first = mid + 1;
            //根据斐波那契数列特性 f[k] = f[k-1] + f[k-2]
            // 因为右半部分排除所以就去掉了f[k - 1]，所以 k = k-2
            k = k - 2;
        } else {
            // 如果为真则找到相应的位置
            if (mid <= last) {
                return mid;
            } else {
                // 出现这种情况是查找到补充的元素
                // 而补充的元素与high位置的元素一样
                return last;
            }
        }
    }
        return result;
}
 // 构造斐波那契数列
    public static int[] fibonacci() {
        int[] finbonacci = new int[30];
        int i = 0;
        finbonacci[0] = 1;
        finbonacci[1] = 1;
        for (i = 2; i < 30; i++) {
            // 后一个元素为前两个元素之和
            finbonacci[i] = finbonacci[i - 1] + finbonacci[i - 2];
        }
        return finbonacci;
    }
    /*
    * 二叉树查找
    * */
    public static Comparable BinaryTreeSearch(Comparable [] data, Comparable target){
            Comparable result = null;
            LinkedBinarySearchTree tree = new LinkedBinarySearchTree();
            for (int i = 0;i< data.length;i ++){
                tree.add(data[i]);
            }
           if (tree.find(target) == target)
               result = target;
        return result;
    }
    /*
    * 分块查找
    * */
    public static Comparable BlockSearch(Comparable[] data ,Comparable target,int n){
        int  a = data.length / n;//每一部分包含的元素
        Comparable result = null;
        Comparable [] b = new Comparable [a];// 创建临时数组
        for (int i = 0;i< data.length; i = i+ a){// 以每个组最小的元素为索引
            if (data[i].compareTo(target) > 0){
                int d = 0;
                for (int j =i -a;j < i;j++){// 将目标组赋给临时数组
                b[d] = data[j];
                d++;
                }
                result = linearSearch(b,target);// 用线性查找来查找临时数组
                break;
            }
                else if (data[i].compareTo(target) == 0){
                result = data[i];
                break;
            }
        }
        return result;
    }

  public static Comparable HashSearch(Comparable[] data ,Comparable target){
     return linearSearch(data,target);
  }
}

